import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Enumeration;
import java.util.Hashtable;
import java.util.List;
import java.util.Set;
import org.jgrapht.alg.CycleDetector;
import org.jgrapht.graph.DefaultDirectedGraph;
import org.jgrapht.traverse.DepthFirstIterator;
/**
 * Graph Builder Class.
 * This class recieves 2 hash tables of nodes, generates the
 * circuit graph and stores it.
 *
 */
public class GraphBuilder {
	/**
	 * Generated graph
	 */
	public DefaultDirectedGraph<Iscas85Node, Iscas85Edge> graph = new DefaultDirectedGraph<Iscas85Node, Iscas85Edge>(Iscas85Edge.class);
	/**
	 * List of input nodes
	 */
	public List<Iscas85Node> inputNodes = new ArrayList<Iscas85Node>();
	/**
	 * List of output nodes
	 */
	public List<Iscas85Node> outputNodes = new ArrayList<Iscas85Node>();
	/**
	 * Hash table that stores nodes by name
	 */
	public Hashtable<String, SimpleNode> nameHash;
	/**
	 * Hash table that stores nodes by identifier
	 */
	public Hashtable<Integer, SimpleNode> identifierHash;

	/**
	 * Constructor for the GraphBuilder class
	 * 
	 * @param nameHash
	 *            Contains graph nodes indexed by name
	 * @param identifierHash
	 *            Contains graph nodes indexed by identifier
	 */
	public GraphBuilder(Hashtable<String, SimpleNode> nameHash, Hashtable<Integer, SimpleNode> identifierHash) {
		this.nameHash = nameHash;
		this.identifierHash = identifierHash;
	}

	/**
	 * Builds the circuit graph
	 * 
	 * @return TRUE if the graph was valid, FALSE otherwise
	 */
	public boolean buildGraph() {
		boolean linked = true;
		boolean noCycle = true;

		// Build nodes
		buildNodes();

		Enumeration<Integer> e = identifierHash.keys();
		while (e.hasMoreElements()) {
			SimpleNode node = identifierHash.get(e.nextElement());
			if (node.i85Gate == NetlistParser.GateType.FROM) {
				nameHash.get(node.i85FanoutName).i85GraphNode.fanoutCount++;
				graph.addEdge(nameHash.get(node.i85FanoutName).i85GraphNode, nameHash.get(node.i85Name).i85GraphNode);
			} else {
				for (int i = 0; i < node.i85FaninList.size(); ++i) {
					Iscas85Node inNode = identifierHash.get(node.i85FaninList.get(i)).i85GraphNode;
					inNode.fanoutCount++;;
					graph.addEdge(inNode, node.i85GraphNode);
				}
			}
		}
		
		// Check fanout values
		DepthFirstIterator<Iscas85Node, Iscas85Edge> it = new DepthFirstIterator<Iscas85Node, Iscas85Edge>(graph);
		while (it.hasNext()) {
			Iscas85Node node = it.next();
			SimpleNode sNode = identifierHash.get(node.identifier);
			if(sNode.i85Gate!=NetlistParser.GateType.FROM && node.fanoutCount != sNode.i85FanoutValue)
			{
				System.out.println("Error on line " + sNode.i85StartLine + ":\n Number of outgoing nodes does not match fanout value\n");
				return false;
			}
		}
		
		// Check cycles
		CycleDetector<Iscas85Node, Iscas85Edge> cd = new CycleDetector<Iscas85Node, Iscas85Edge>(graph);
		noCycle = !cd.detectCycles();
		if (!noCycle)
			System.out.println("Graph integrity error: the graph contains cycles");

		return linked && noCycle;
	}

	/**
	 * Build graph nodes from the abstract tree nodes
	 */
	private void buildNodes() {
		Enumeration<Integer> e = identifierHash.keys();

		// Loop through all the elements
		while (e.hasMoreElements()) {
			SimpleNode node = identifierHash.get(e.nextElement());
			
			if (node.i85Gate == NetlistParser.GateType.INPT || node.i85Gate == NetlistParser.GateType.BUFF || node.i85Gate == NetlistParser.GateType.FROM) {
				node.i85GraphNode = new Iscas85FixValue();
				node.i85GraphNode.nodeType = node.i85Gate;
				node.i85GraphNode.sa0 = node.i85SA0;
				node.i85GraphNode.sa1 = node.i85SA1;
				node.i85GraphNode.value = -1;
				node.i85GraphNode.name = node.i85Name;
				node.i85GraphNode.identifier = node.i85Id;
				graph.addVertex(node.i85GraphNode);

				// Check if input node
				if (node.i85Gate == NetlistParser.GateType.INPT) {
					inputNodes.add(node.i85GraphNode);
				}
				
				// Check if output node
				if (node.i85FanoutValue == 0 && node.i85Gate != NetlistParser.GateType.FROM) {
					outputNodes.add(node.i85GraphNode);
				}
			} else {
				node.i85GraphNode = new Iscas85Logic();
				node.i85GraphNode.nodeType = node.i85Gate;
				node.i85GraphNode.sa0 = node.i85SA0;
				node.i85GraphNode.sa1 = node.i85SA1;
				node.i85GraphNode.value = -1;
				node.i85GraphNode.name = node.i85Name;
				node.i85GraphNode.identifier = node.i85Id;
				((Iscas85Logic) node.i85GraphNode).completed = 0;
				((Iscas85Logic) node.i85GraphNode).faninValues = new byte[node.i85FaninValue];
				graph.addVertex(node.i85GraphNode);

				// Check if output node
				if (node.i85FanoutValue == 0) {
					outputNodes.add(node.i85GraphNode);
				}
			}
		}
	}

	/**
	 * Exports graph structure to a dot file
	 * 
	 * @param filename
	 *            Name of the output file
	 * @param graphName
	 *            Name of the circuit graph
	 * @throws IOException
	 */
	public void exportDotFile(String filename, String graphName, boolean append) throws IOException {
		// Create output stream
		FileWriter outFile = new FileWriter(filename);
		PrintWriter out = new PrintWriter(outFile);
		String labels = "\t// Node labels and definitions\n";
		out.println("digraph " + graphName + " {\n\n\t// Node connections");
		DepthFirstIterator<Iscas85Node, Iscas85Edge> it = new DepthFirstIterator<Iscas85Node, Iscas85Edge>(graph);
		while (it.hasNext()) {
			Iscas85Node node = it.next();
			String value = append ? " = " + node.value : "";
			if(inputNodes.contains(node)) {
				labels += "\t" + node.identifier + " [label=\"" + node.nodeType + "." + node.name + value + "\" shape=\"invhouse\"];\n";
			}
			else if(outputNodes.contains(node)) {
				labels += "\t" + node.identifier + " [label=\"" + node.nodeType + "." + node.name + value + "\" shape=\"house\"];\n";
			}
			else {
				labels += "\t" + node.identifier + " [label=\"" + node.nodeType + "." + node.name + value + "\" shape=\"box\"];\n";
			}
			Set<Iscas85Edge> children = graph.outgoingEdgesOf(node);
			for (Iscas85Edge edge : children) {
				out.println("\t" + graph.getEdgeSource(edge).identifier + " -> " + graph.getEdgeTarget(edge).identifier + ";");
			}
		}
		out.print("\n" + labels + "\n}");
		out.close();
	}
}
